import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @author 03010570
 * @date 2020/06/29
 * describe:    LeetCode:   215、数组中的第 K 个元素 https://leetcode-cn.com/problems/kth-largest-element-in-an-array/
 */
public class LeetCode_215 {

    public static void main(String[] args) {
        int[] num = {4,5,1,6,2,7,3,8};
        int k=3;
        System.out.println(findKthLargest(num, k));
    }

        /**
         * method 1:    优先队列实现小顶堆
         *  使用 JDK 自带的优先队列实现 k 小顶堆。
         *  第 K 大元素返回 小顶堆的最上面的值即可
         * @param nums
         * @param k
         * @return
         */
    public static int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(k, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1.compareTo(o2);
            }
        });
        for (int num : nums) {
            if(maxHeap.size() !=k){
                maxHeap.add(num);
            }else if(maxHeap.peek() <num){
                Integer poll = maxHeap.poll();
                maxHeap.add(num);
            }
        }
        return maxHeap.peek();
    }
}
